week6 HW 戴偉璿

第一題

假設一開始的陣列都只有一格

a.

時間複雜度的部份,我們先假設n=2a+b;a,bN;b<2a+1n=2^a+b;a,b\in\mathbb{N};b<2^{a+1},很顯然所需的複製次數為k=0a2k=2a+11\displaystyle\sum^a_{k=0}2^k=2^{a+1}-1,插入元素的複雜度為bb,其時間雜度為O(2a+1+b)=O(2n)=O(n)O(2^{a+1}+b)=O(2n)=O(n)

空間複雜度的部份,最終所需的空間為O(2a+1)=O(2n)=O(n)O(2^{a+1})=O(2n)=O(n)

b.

在插入新元素時,會先新增一個比原大小多一的陣列,並且將舊有的所有資料複製過去,由於每次都只會開「剛剛好」,因此空間複雜度為O(n)O(n)

但是每次都會將舊有的所有資料複製過去,在插入第二個元素時有一個元素需要複製,拆入第二個元素時需要複製兩個元素…插入第nn個元素時需要複製n1n-1個元素。所需時間複雜度為每次操作時所需複製元素數目的總和,i=1n1=(n1)n2\displaystyle\sum^{n-1}_{i=1}=\cfrac{(n-1)n}{2}bigO=O(n2)big-O=O(n^2)

第二題

事先聲明:nk=n\cfrac{n}{k}=n除以kk之後無條件捨去取至整數(跟C++一樣)

a.

預處理:O(NK)O(NK)

總詢問:O(Q×NK)O(Q\times \cfrac{N}{K})









b.

根據2.(a)2.(a)的答案,預處理複雜度為O(NK)O(NK),總詢問複雜度為O(Q×NK)O(Q\times \cfrac{N}{K})。又O(N)=O(Q)O(N)=O(Q)

因此NK=Q×NKK=NNK=Q\times \cfrac{N}{K}\Rightarrow K=\sqrt{N}

c.

jump[i][j1][1]+jump[jump[i][j1]][1]][K][0]jump[ i ][ j-1 ][ 1 ]+jump[ jump[ i ][ j-1 ] ][ 1 ] ][ K ][ 0 ]

e.

題目怪怪的?條件為j=1j=1j>0j>0

if  j=1if\;j=1 jump[i][j][l]=jump[i][K][0]jump[i][j][l]=jump[i][K][0]

if  j>1if\;j>1 jump[i][j][l]=jump[i][j1][l]+jump[jump[i][j1]][l]][K][l1]jump[i][j][l]=jump[i][j-1][l]+jump[jump[i][j-1] ][l] ][K][l-1]